//
// Created by Administrator on 2021/11/11.
//

/*#include <iostream>

int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}*/

#include <stdio.h>
#include <stdlib.h>
//线性表的顺序表示
#define maxSize 100 //自定义线性表的最大长度
#define ElemType int //自定义Elemtype类型

/*线性表的链式存储*/
typedef struct LNode {//定义单链表结点类型
    ElemType data;//数据域
    struct LNode *next;//指针域
} LNode, *LinkList;
/*结点的实现：malloc();realloc();sizeof();free();*/
/*动态分配：*/LinkList p = (LNode *) malloc(sizeof(LNode));
/*动态释放：free(p);*/

/*初始化一个空的链表（不带头节点）*/
bool InitList(LinkList &L) {
    L = NULL;//空表，暂时还没有结点
    return true;
}

/*判断链表（不带头节点）是否为空*/
bool Empty(LinkList L) {
    if (L == NULL) {
        return true;
    } else {
        return false;
    }
}

bool Empty01(LinkList L) {
    return (L == NULL);
}

/*初始化链表（带头结点）*/
bool InitListWithHead(LinkList &L) {
    L = (LNode *) malloc(sizeof(LNode));//分配一个头结点
    if (L == NULL) {
        return false;//内存不足分配失败
    } else {
        L->next = NULL;//头结点之后还没有结点
    }
    return true;
}

/*判断链表（带头节点）是否为空*/
bool EmptyWithHead(LinkList L) {
    if (L->next == NULL) {
        return true;
    } else {
        return false;
    }
}

/*单链表的基本操作*/
/*头插法：每次在头结点之后插入元素，每次插入的点都作为链表的第一个结点*/
LinkList List_HeadInsert(LinkList &L) {
    LNode *s;
    int x;
    L = (LinkList) malloc(sizeof(LNode));//创建头结点
    L->next = NULL;//初始化
    scanf("%d", &x);//输入插入的值
    while (x != 9999) {
        s = (LNode *) malloc(sizeof(LNode));//创建新的结点
        s->data = x;//传入值
        s->next = L->next;//新节点连到主线上
        L->next = s;//新节点放到头结点后面
        scanf("%d", &x);
    }
    return L;
}

/*尾插发：每次均在表尾部插入元素*/
LinkList List_TailInsert(LinkList &L) {
    int x;
    L = (LinkList) malloc(sizeof(LNode));//创建头结点
    LNode *s, *r = L;//r为表尾指针(此时头结点=尾结点)
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *) malloc(sizeof(LNode));//创建新的结点
        s->data = x;//传入值
        r->next = s;//s连入主链最后面
        r = s;//更新尾结点的指针的值
        scanf("%d", &x);
    }
    r->next = NULL;//尾结点指针置空
    return L;
}

/*按序号查找结点值*/
LNode *GetElem(LinkList L, int i) {
    int j = 1;
    LNode *p = L->next;//p在第1个位置
    if (i == 0) {
        return L;//返回头节点（第0个）
    }
    if (i < 1) {
        return NULL;//无效值
    }
    while (p && j < i) {//查找位置从第2个开始
        p = p->next;
        j++;
    }
    return p;
}

/*按值查找表结点*/
LNode *LocateElem(LinkList L, ElemType e) {
    LNode *p = L->next;//p在第1个位置
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p;//p肯能有值，也可能为空
}

/*后插：在指定结点后面插入*/
bool InsertNextNode(LNode *p, ElemType e) {
    if (p == NULL) {
        return false;
    }
    LNode *s = (LNode *) malloc(sizeof(LNode));//创建新的结点
    if (s == NULL) {
        return false;//内存分配失败
    }
    s->data = e;//赋值
    s->next = p->next;//新节点连到主链
    p->next = s;//两条链合并
    return true;
}

/*插入（带头结点）*/
bool ListInsert(LinkList &L, int i, ElemType e) {
    if (i < 1) {
        return false;//位序不合法
    }
    int pj = 0;//p在第几个结点
    LNode *p = L;//p是扫描到的节点
    while (p != NULL && pj < i - 1) {//找到第i-1位置的结点
        p = p->next;
        pj++;
    }
    return InsertNextNode(p, e);
}

/*删除结点*/
bool ListDelete(LinkList &L, int i, ElemType &e) {
    LNode *p = GetElem(L, i - 1);
    /*找到i的前驱结点*/
    if (p == NULL || p->next == NULL) {
        return false;
    }
    LNode *q = p->next;
    e = q->data;//将删除的值传出来
    p->next = q->next;
    free(q);
    return true;
}

/*删除指定结点p*/
bool DeleteNode(LNode *p) {
    if (p == NULL) {
        return false;
    }
    LNode *q = p->next;//p的后继结点(可能为null，有bug)
    p->data = q->data;//后继节点覆盖p的值
    p->next = q->next;
    free(q);
    return true;
}

/*双链表*/
typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next;//前驱和后继指针
} DNode, *DLinkList;

/*初始化双链表（带头结点）*/
bool InitDLinkList(DLinkList &L) {
    L = (DNode *) malloc(sizeof(DNode));//分配一个头结点
    if (L == NULL) { return false; }//内存不足,分配失败
    L->prior = NULL;//头结点的prior永远指向null
    L->next = NULL;//头结点之后暂时还没有节点
    return true;
}

/*判断双链表是否为空(带头结点)*/
bool Empty(DLinkList L) {
    if (L->next == NULL) { return true; }
    else { return false; }
}

/*在p结点之后插入s结点*/
bool InsertNextDNode(DNode *p, DNode *s) {
    if (p == NULL || s == NULL) {
        return false;//非法传参
    }
    s->next = p->next;//将结点*s插入到结点*p之后（新节点next申请连到主链）
    if (p->next != NULL) {
        p->next->prior = s;//如果后面有主链（主链接受）
    }
    s->prior = p;//（新节点prior申请连接到主链）
    p->next = s;//（主链接受）
    return true;
}

/*删除p结点的后继节点*/
bool DeleteNextDNode(DNode *p) {
    if (p == NULL) {
        return false;
    }
    DNode *q = p->next;//q为p的后继节点
    if (q == NULL) {
        return false;//p没有后继结点
    }
    p->next = q->next;
    if (q->next != NULL) {//q结点后面还有结点
        q->next->prior = p;
    }
    free(q);
    return true;
}

/*销毁链表*/
void DestoryList(DLinkList &L) {
    while (L->next != NULL) {
        DeleteNextDNode(L);//销毁L的下一个节点
    }
    free(L);
    L = NULL;
}


/*循环单链表*/
/*初始化：L->next=L*/
/*判空条件：L->next==L*/
/*判断是否为表尾结点：p->next==L*/

/*循环双链表*/
/*初始化：L->next=L;
 * L->prior=L*/
/*判空条件：L->next==L*/
/*是否为表尾结点：p->next==L*/